package com.Leetcode;

import com.Util.ProduceTree;
import com.structure.TreeNode;

public class Index105BuildTree {
	public static void main(String[] args) {
		int[] preorder = {1,2,3}, inorder = {2,3,1};
		Index105BuildTree build = new Index105BuildTree();
		TreeNode root = build.buildTree(preorder, inorder);
		System.out.println(ProduceTree.treeNodeToString(root));
	}
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		TreeNode root = buildBinaryTree(preorder,inorder,0,preorder.length-1,0);
		return root;
    }
	
	TreeNode buildBinaryTree(int[] preorder,int[] inorder,int low,int high,int index){
		if(high < low) return null;
		TreeNode node = new TreeNode(preorder[index]);
		int pos = low;
		for(int i = low;i <= high; i ++)
			if(inorder[i] == preorder[index]) {
				pos = i;
			}
		node.left = buildBinaryTree(preorder,inorder,low,pos-1,index+1);
		node.right = buildBinaryTree(preorder,inorder,pos+1,high,index+(pos-low)+1);
		return node;
	}
}
